package com.lw.leetcode.str.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * str
 * 395. 至少有 K 个重复字符的最长子串
 *
 * @author liw
 * @version 1.0
 * @date 2021/7/30 14:11
 */
public class LongestSubstring {

    public static void main(String[] args) {
        LongestSubstring test = new LongestSubstring();

//        String str = "aabbabc";
//        int k = 3;

        // "baaabcb" 3
        String str = "baaabcb";
        int k = 3;
        System.out.println(test.longestSubstring(str, k));
    }

    private int k;
    private int max;
    private char[] chars;

    public int longestSubstring(String str, int k) {
        this.k = k;
        this.chars = str.toCharArray();
        this.max = 0;
        find(0, str.length() - 1);
        return max;
    }

    private void find(int st, int end) {
        Map<Character, List<Integer>> map = new HashMap<>(26, 1);
        int[] arr = new int[26];
        for (int i = st; i <= end; i++) {
            arr[chars[i] - 'a']++;
            List<Integer> list = map.computeIfAbsent(chars[i], v -> new ArrayList<>());
            list.add(i);
        }
        int[] splitArr = new int[end - st + 1];
        int index = 0;
        boolean flag = true;
        for (int i = 0; i < 26; i++) {
            if (arr[i] < k) {
                char c = (char) ('a' + i);
                List<Integer> list = map.get(c);
                if (list != null) {
                    for (Integer value : list) {
                        splitArr[index++] = value;
                    }
                }
            } else {
                flag = false;
            }
        }
        if (flag) {
            return;
        }
        if (index == 0) {
            max = Math.max(max, end - st + 1);
            return;
        }
        splitArr = Arrays.copyOf(splitArr, index);
        Arrays.sort(splitArr);
        int s = st - 1;
        for (int i = 0; i < index; i++) {
            if (splitArr[i] - s - 1 > max) {
                find(s + 1, splitArr[i] - 1);
            }
            s = splitArr[i];
        }
        if (end - s > max) {
            find(s + 1, end);
        }
    }

}
